package com.xucy.springboot.code;

import lombok.Data;

import java.util.*;

/**
 * @Author xucy
 * @Date 2019-09-29 15:11
 * @Description
 **/

public class Test1 {




    public static void test1(){

    }

    //给一个整数，将整数调换位置 11232 -》 23211
    public static int test2(int x){
        int res = 0;
        int of = ((1 << 31) - 1) / 10;
        while (x != 0) {
            if (Math.abs(res) >of)
                return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
    //给一个整数，将整数调换位置 11232 -》 23211
    public static int test3(int x){
        int res=0;
        while (x!=0){

            res=res*10+x%10;
            x/=10;

        }

        return res;
    }

    //回文数判断
    public static boolean test4(int x){
        //边界判断
        if (x < 0)
            return false;
        int div = 1;

        while (x / div >= 10)
            div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right)
                return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }

    //自己的回文数判断 1221 true  -1221 false  1231 false
    public static boolean test5(int x){
        if(x<0){
            return false;
        }

        int i=1;
        //对i进行乘10操作，从而得到x一共是多少位
        while(x/i>=10)
            i=i*10;

        while(x>0){
            //得到左边第一位
            int left=x/i;
            //得到右边第一位
            int right=x%10;
            if(left!=right){
                return false;
            }
            //计算新的x值，去掉左边和右边的第一位
            x=(x%i)/10;
            i=i/100;
        }
        return true;
    }

    //自己的回文数判断
    public static boolean test6(int x){
        StringBuilder stringBuilder = new StringBuilder(x + "");
        String s=stringBuilder.reverse().toString();
        System.out.println("小明");
        return s.equals(x+"");
    }


    //罗马数字转整数
    public static int romanToInt(String s) {
        String[] roman = { "IV", "IX", "XL", "XC", "CD", "CM", "I", "V", "X", "L", "C", "D", "M" };
        int[] nums = { 4, 9, 40, 90, 400, 900, 1, 5, 10, 50, 100, 500, 1000 };
        int num = 0;
        while (s.length() > 0) {
            for (int i = 0; i < roman.length; i++) {
                if (s.startsWith(roman[i])) {
                    num += nums[i];
                    s = s.substring(roman[i].length());
                    break;
                }
            }
        }
        return num;
    }


    //编写一个函数来查找字符串数组中的最长公共前缀。
    public static String searchCommonPre(String[] strs) {

        if(strs.length==0){
            return "";
        }

        String result=strs[0];

        for(int i=1;i<strs.length;i++){
            int j=0;
            for(;j<result.length()&&j<strs[i].length();j++){
                if(result.charAt(j)!=strs[i].charAt(j)){
                    break;
                }
            }
            result=result.substring(0,j);
        }

        return result;
    }


    //有效的括号
    public static boolean validKh(String str){
        Map map=new HashMap();
        map.put(")","(");
        map.put("]","[");
        map.put("}","{");
        Stack<String> stack=new Stack<>();

        //判断str如果是奇数或者为空直接返回false
        if(str.length()<0||str.length()%2>0){
            return false;
        }

        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            //如果包含，则去判断是否栈中有对应的开，不包含说明是开，直接添加
            if(map.containsKey(c+"")){
                String pop=stack.isEmpty()?"#":stack.pop();
                if(!pop.equals(map.get(c+""))){
                    return false;
                }
            }else{
                stack.push(c+"");
            }
        }

        return stack.isEmpty();
    }

    //对一个排序数组进行去重。[1,2,3,3,4,4,5] 返回[1,2,3,4,5,3,4]
    public static int test7(int[] arrs){
        if(arrs.length==0){
            return 0;
        }
        //定义一个慢指针i,一个快指针j.当不重复就增加慢指针，重复就不增加慢指针
        int i=0;
        for(int j=1;j<arrs.length;j++){
            if(arrs[j]!=arrs[i]){
                i++;
                arrs[i]=arrs[j];
            }
        }
        for(int z=0;z<arrs.length;z++){
            System.out.println(arrs[z]);
        }
        return i+1;
    }

    //给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
    public static int test8(int[] nums, int val){

        if(nums.length==0){
            return 0;
        }
        int i=0;
        for(int j=0;j<nums.length;j++){
            if(nums[j]!=val){
                nums[i]=nums[j];
                i++;
            }
        }
        for(int z=0;z<nums.length;z++){
            System.out.println(nums[z]);
        }

        return i;
    }

    //给定str1 str2，找出str2在str1中最开始的位置
    public static int test9(String haystack, String needle){
        int preLength=haystack.length(),postLength=needle.length();

        if(preLength==0 ||postLength==0){
            return 0;
        }

        for(int index=0;index<haystack.length();index++){
            //如果原字符串始终都不等于后字符串的开头，就一直循环
            if(haystack.charAt(index)!=needle.charAt(0)){
                continue;
            }
            //如果查找到相同的位置时候，当前位置加后字符串大小大于原字符串大小。那就不用比了，肯定找不到
            if(index+postLength>preLength){
                break;
            }
            int tmp=index+1;
            for(;tmp<index+postLength;tmp++){
                if(haystack.charAt(tmp)!=needle.charAt(tmp-index)){
                    break;
                }
            }
            if(tmp==index+postLength)
              return index;
        }

        return -1;
    }


    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
    // 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    public static int  test10(int[] nums, int target){
        if(nums.length==0){
              return 0;
        }

        for(int j=0;j<nums.length;j++){
            if(nums[j]<target){
                continue;
            }
            if(nums[j]>=target){
                return j;
            }
        }
        
       return 0;
    }

    //最大子序和
    public static int  test11(int[] nums){

        if(nums.length==0){
            return 0;
        }

        int ans=nums[0];
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(sum>0){
                sum+=nums[i];
            }else{
                sum=nums[i];
            }

            ans=Math.max(ans,sum);
        }

        return ans;
    }

    //给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
    public static int  lengthOfLastWord(String s){

        if(s.trim().length()==0){
            return 0;
        }
        int end=s.length()-1;
        while(s.charAt(end)==' ') {
            end--;
            if(end<0){
               return 0;
            }
        }

        int start=end;
        while (start>=0&& s.charAt(start)!=' '){
            start--;
        }
        return end-start;
    }
    //给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0
    public static String addBinary(String a, String b) {
        StringBuilder sb=new StringBuilder();

        //定义一个变量看是否进位
        int ca=0;
        for(int i=a.length()-1,j=b.length()-1;i>=0||j>=0;i--,j--){
            int sum=ca;
            sum+= i>=0? a.charAt(i)-'0' :0;
            sum+= j>=0? b.charAt(j)-'0' :0;

            sb.append(sum%2);
            ca=sum/2;
        }
        if(ca==1) sb.append("1");

        return sb.reverse().toString();
    }

    //给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
    //你可以假设除了整数 0 之外，这个整数不会以零开头。
    public static int[] plusOne(int[] digits) {

        for(int i=digits.length-1;i>=0;i--){
            digits[i]++;
            digits[i]=digits[i]%10;
            if(digits[i]!=0){
                return digits;
            }
        }

        digits=new int[digits.length+1];
        digits[0]=1;
        return digits;
    }

    //
    public static int mySqrt(int x) {
        int  s=x;
        if(x==0) return 0;
        return ((int)(sqrts(s,x)));
    }

    public static double sqrts(int s,double x){
        double res = (x + s / x) / 2;
        if (res == x) {
            return x;
        } else {
            return sqrts(s,res);
        }
    }

    //实现 int sqrt(int x) 函数。
    //计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
    public static int mySqrt1(int x) {
        //使用二分查找法
        long left=0;
        long right=x/2+1;


        while(left<right){
            long mid = (left + right + 1)/2;
            if ( mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }

        return (int)left;
    }

    @Data
    public static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }

    public static ListNode deleteDuplicates(ListNode head) {
        ListNode current=head;

        while(current!=null && current.next!=null){
            if(current.val==current.next.val){
                current.next=current.next.next;
            }else{
                current=current.next;
            }
        }

        return head;
    }

    public static void main(String[] args) {
//        test1();
//
//        System.out.println(test3(-2147483412));
//        System.out.println(test6(1022101));
//        System.out.println(romanToInt("MCMXCIV"));
//
//        System.out.println(searchCommonPre(new String[]{"xuchen","xujian","xulin"}));
//        System.out.println(validKh("(({[(){}()[{)]]}))"));

//        System.out.println(test7(new int[]{1,2,3,3,4,4,5}));

//        System.out.println(test8(new int[]{1, 2, 3, 3, 4, 4, 5},3));
//        System.out.println(test9("hello","lo"));
//        System.out.println(lengthOfLastWord("a"));

//        System.out.println(Arrays.toString(plusOne(new int[]{9,9,9,9})));

//        System.out.println(addBinary("1","111"));
        System.out.println(mySqrt1(2));
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(1);
        ListNode listNode3=new ListNode(2);
        ListNode listNode4=new ListNode(2);
        ListNode listNode5=new ListNode(3);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        ListNode listNode = deleteDuplicates(listNode1);
        System.out.println(listNode);
    }




}
